#!/usr/bin/env python
# -*- coding: utf-8 -*-
#author: João Caixinha


class BinaryTree:
    '''
    esta class representa uma arvore binaria representa por uma tabela com
    quatro arrays, chave, nó pai, nó á esquerda e nó á direita.
    '''
    def __init__(self,N):
        self.N = N
        self.apontadores_memoria = Stack(N)
        for k in range(N):
            self.apontadores_memoria.push(k)
        self.key =  [0 for k in range(N)]
        self.left = [0 for k in range(N)]
        self.right = [0 for k in range(N)]
        self.p = [0 for k in range(N)]

        self.BF = [0 for k in range(N)]
        
        self.head = -1

        
    def __str__(self):
        s = '---------------------------------------\n'
        for x in range(self.N - 1, self.head - 1, -1):
            s += str(x) + '- |' + str(self.key[x]) + '|' + str(self.p[x]) + '|' + str(self.left[x]) + '|' + str(self.right[x]) + '|' \
            +   str(self.BF[x]) + '\n'
            s += '---------------------------------------\n'
        return s
    
    '''
    malloc, reserva memoria para uma novo nó
    '''
    def malloc(self, k):
        x = self.apontadores_memoria.pop()
        self.key[x] = k
        self.left[x] = None
        self.right[x] = None
        self.p[x] = None
        return x
    
    '''
    insert, insere o nó numa dada posição na memoria com o pai top, e o leftOrRight
    representa se este está á esquerda ou direita do pai.
    '''
    def insert(self, x, top, leftOrRight, moveHead):
                self.p[x] = top
                if top != None:
                        if leftOrRight == None:
                            pass
                        elif leftOrRight:
                                self.left[top] = x
                        elif not leftOrRight:
                                self.right[top] = x
                if moveHead:
                    self.head = x
    
    '''
    removeNode, elimina um nó
    '''
    def removeNode(self,x):
        
        self.key[x] = 0
        self.p[x] = 0
        self.left[x] = 0
        self.right[x] = 0
        self.BF[x] = 0
        
    '''
    copyNode, copia um nó para outra posição de memoria
    '''    
    def copyNode(self, rem):
        self.removeNode(rem)
        self.apontadores_memoria.push(rem)
                
            
class Stack:
        def __init__(self, N):
                self.top = -1
                self.S = [0 for k in range(N)]
                pass
        
        def stack_empty(self):
                if self.top < 0:
                        return True
                else:
                        return False
        
        def push(self, x):
                self.top += 1
                self.S[self.top] = x
                pass
        
        def pop(self):
                if self.stack_empty():
                        return "underflow"
                else:
                        self.top -= 1
                        return self.S[self.top+1]
                pass
            
        def __str__(self):
                s = ""
                s += str(self.top+1) + ": "
                for k in range(0, self.top+1):
                        s += ' ' + str(self.S[k])
                return s
        pass

